The maximum clique problem is a well known NP-Hard problem with applicationsin data mining, network analysis, information retrieval and many other areasrelated to the World Wide Web. There exist several algorithms for the problemwith acceptable runtimes for certain classes of graphs, but many of them areinfeasible for massive graphs. We present a new exact algorithm that employsnovel pruning techniques and is able to find maximum cliques in very large,sparse graphs quickly. Extensive experiments on different kinds of syntheticand real-world graphs show that our new algorithm can be orders of magnitudefaster than existing algorithms. We also present a heuristic that runs ordersof magnitude faster than the exact algorithm while providing optimal ornear-optimal solutions. We illustrate a simple application of the algorithms indeveloping methods for detection of overlapping communities in networks.
展开▼
